/*
 * Copyright (c) 2004-2007 Apple Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 *
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_LICENSE_HEADER_END@
 */
/*
 Implementation of the weak / associative references for non-GC mode.
 */


#include "objc-private.h"
#include <objc/message.h>
#include <map>

#if _LIBCPP_VERSION
#   include <unordered_map>
#else
#   include <tr1/unordered_map>
using namespace tr1;
#endif


// wrap all the murky C++ details in a namespace to get them out of the way.

namespace objc_references_support {
    struct DisguisedPointerEqual {
        bool operator()(uintptr_t p1, uintptr_t p2) const {
            return p1 == p2;
        }
    };
    
    struct DisguisedPointerHash {
        uintptr_t operator()(uintptr_t k) const {
            // borrowed from CFSet.c
#if __LP64__
            uintptr_t a = 0x4368726973746F70ULL;
            uintptr_t b = 0x686572204B616E65ULL;
#else
            uintptr_t a = 0x4B616E65UL;
            uintptr_t b = 0x4B616E65UL;
#endif
            uintptr_t c = 1;
            a += k;
#if __LP64__
            a -= b; a -= c; a ^= (c >> 43);
            b -= c; b -= a; b ^= (a << 9);
            c -= a; c -= b; c ^= (b >> 8);
            a -= b; a -= c; a ^= (c >> 38);
            b -= c; b -= a; b ^= (a << 23);
            c -= a; c -= b; c ^= (b >> 5);
            a -= b; a -= c; a ^= (c >> 35);
            b -= c; b -= a; b ^= (a << 49);
            c -= a; c -= b; c ^= (b >> 11);
            a -= b; a -= c; a ^= (c >> 12);
            b -= c; b -= a; b ^= (a << 18);
            c -= a; c -= b; c ^= (b >> 22);
#else
            a -= b; a -= c; a ^= (c >> 13);
            b -= c; b -= a; b ^= (a << 8);
            c -= a; c -= b; c ^= (b >> 13);
            a -= b; a -= c; a ^= (c >> 12);
            b -= c; b -= a; b ^= (a << 16);
            c -= a; c -= b; c ^= (b >> 5);
            a -= b; a -= c; a ^= (c >> 3);
            b -= c; b -= a; b ^= (a << 10);
            c -= a; c -= b; c ^= (b >> 15);
#endif
            return c;
        }
    };
    
    struct ObjectPointerLess {
        bool operator()(const void *p1, const void *p2) const {
            return p1 < p2;
        }
    };
    
    struct ObjcPointerHash {
        uintptr_t operator()(void *p) const {
            return DisguisedPointerHash()(uintptr_t(p));
        }
    };
    
    // STL allocator that uses the runtime's internal allocator.
    
    template <typename T> struct ObjcAllocator {
        typedef T                 value_type;
        typedef value_type*       pointer;
        typedef const value_type *const_pointer;
        typedef value_type&       reference;
        typedef const value_type& const_reference;
        typedef size_t            size_type;
        typedef ptrdiff_t         difference_type;
        
        template <typename U> struct rebind { typedef ObjcAllocator<U> other; };
        
        template <typename U> ObjcAllocator(const ObjcAllocator<U>&) {}
        ObjcAllocator() {}
        ObjcAllocator(const ObjcAllocator&) {}
        ~ObjcAllocator() {}
        
        pointer address(reference x) const { return &x; }
        const_pointer address(const_reference x) const {
            return x;
        }
        
        pointer allocate(size_type n, const_pointer = 0) {
            return static_cast<pointer>(::malloc(n * sizeof(T)));
        }
        
        void deallocate(pointer p, size_type) { ::free(p); }
        
        size_type max_size() const {
            return static_cast<size_type>(-1) / sizeof(T);
        }
        
        void construct(pointer p, const value_type& x) {
            new(p) value_type(x);
        }
        
        void destroy(pointer p) { p->~value_type(); }
        
        void operator=(const ObjcAllocator&);
        
    };
    
    template<> struct ObjcAllocator<void> {
        typedef void        value_type;
        typedef void*       pointer;
        typedef const void *const_pointer;
        template <typename U> struct rebind { typedef ObjcAllocator<U> other; };
    };
    
    typedef uintptr_t disguised_ptr_t;
    inline disguised_ptr_t DISGUISE(id value) { return ~uintptr_t(value); }
    inline id UNDISGUISE(disguised_ptr_t dptr) { return id(~dptr); }
    //一个关联对象的封装
    class ObjcAssociation {
        uintptr_t _policy; // 关联策略
        id _value; // 关联值
    public:
        ObjcAssociation(uintptr_t policy, id value) : _policy(policy), _value(value) {}
        ObjcAssociation() : _policy(0), _value(nil) {}
        
        uintptr_t policy() const { return _policy; }
        id value() const { return _value; }
        
        bool hasValue() { return _value != nil; } // 关联对象是否有值
    };
    
#if TARGET_OS_WIN32
    typedef hash_map<void *, ObjcAssociation> ObjectAssociationMap;
    typedef hash_map<disguised_ptr_t, ObjectAssociationMap *> AssociationsHashMap;
#else
    typedef ObjcAllocator<std::pair<void * const, ObjcAssociation> > ObjectAssociationMapAllocator;
    // 可以理解为一个被关联对象的所有关联对象
    class ObjectAssociationMap : public std::map<void *, ObjcAssociation, ObjectPointerLess, ObjectAssociationMapAllocator> {
    public:
        void *operator new(size_t n) { return ::malloc(n); }
        void operator delete(void *ptr) { ::free(ptr); }
    };
    typedef ObjcAllocator<std::pair<const disguised_ptr_t, ObjectAssociationMap*> > AssociationsHashMapAllocator;
    // 维护key:被关联object的地址, value: ObjectAssociationMap的映射, 即被关联对象的全部关联记录;
    class AssociationsHashMap : public unordered_map<disguised_ptr_t, ObjectAssociationMap *, DisguisedPointerHash, DisguisedPointerEqual, AssociationsHashMapAllocator> {
    public:
        void *operator new(size_t n) { return ::malloc(n); }
        void operator delete(void *ptr) { ::free(ptr); }
    };
#endif
}

using namespace objc_references_support;

// class AssociationsManager manages a lock / hash table singleton pair.
// Allocating an instance acquires the lock, and calling its assocations()
// method lazily allocates the hash table.

spinlock_t AssociationsManagerLock; // mutex_t 互斥锁

// 一个单例类, 维护全部的关联内容
class AssociationsManager {
    // associative references: object pointer -> PtrPtrHashMap.
    static AssociationsHashMap *_map; // 静态的说明维护所有的对象的关联对象
public:
    AssociationsManager()   { AssociationsManagerLock.lock(); } // mutex_t 互斥锁: 加锁
    ~AssociationsManager()  { AssociationsManagerLock.unlock(); } // mutex_t 互斥锁: 解锁
    
    AssociationsHashMap &associations() { // 是一个无序的哈希表, 维护了从对象地址到 ObjectAssociationMap 的映射;
        if (_map == NULL)
            _map = new AssociationsHashMap();
        return *_map;
    }
};

AssociationsHashMap *AssociationsManager::_map = NULL; // 全局的说明所有的关联是一个单利对象管理的

// expanded policy bits.
// 有人很好奇怎么跟 objc_AssociationPolicy 不一样, 其实objc_AssociationPolicy是把runtime的OBJC_ASSOCIATION_SETTER 细分了, 仔细研究你就会发现objc_AssociationPolicy 与OBJC_ASSOCIATION_SETTER 有很大的联系的
enum {
    OBJC_ASSOCIATION_SETTER_ASSIGN      = 0,
    OBJC_ASSOCIATION_SETTER_RETAIN      = 1,
    OBJC_ASSOCIATION_SETTER_COPY        = 3,    // NOTE:  both bits are set, so we can simply test 1 bit in releaseValue below.
    OBJC_ASSOCIATION_GETTER_READ        = (0 << 8),
    OBJC_ASSOCIATION_GETTER_RETAIN      = (1 << 8),
    OBJC_ASSOCIATION_GETTER_AUTORELEASE = (2 << 8)
};

/** 不多解释. 看完_object_set_associative_reference看这个很简单
 * 关联引用对象
 ** Objective-C: objc_getAssociatedObject 最终会调用 _object_get_associative_reference来获取关联对象。
 ** 底层: _object_get_associative_reference
 * object : 被关联对象
 * key    : 可以认为是一个属性名
 */
id _object_get_associative_reference(id object, void *key) {
    id value = nil;
    uintptr_t policy = OBJC_ASSOCIATION_ASSIGN;
    {
        AssociationsManager manager;
        AssociationsHashMap &associations(manager.associations());
        disguised_ptr_t disguised_object = DISGUISE(object);
        AssociationsHashMap::iterator i = associations.find(disguised_object);
        if (i != associations.end()) {
            ObjectAssociationMap *refs = i->second;
            ObjectAssociationMap::iterator j = refs->find(key);
            if (j != refs->end()) {
                ObjcAssociation &entry = j->second;
                value = entry.value();
                policy = entry.policy();
                if (policy & OBJC_ASSOCIATION_GETTER_RETAIN) {
                    objc_retain(value);
                }
            }
        }
    }
    if (value && (policy & OBJC_ASSOCIATION_GETTER_AUTORELEASE)) {
        objc_autorelease(value);
    }
    return value;
}

/**
 * 判断关联值类型
 * value  : 值
 * policy : 关联策略
 */
static id acquireValue(id value, uintptr_t policy) {
    switch (policy & 0xFF) {
        case OBJC_ASSOCIATION_SETTER_RETAIN:
            return objc_retain(value); // retain value
        case OBJC_ASSOCIATION_SETTER_COPY:
            return ((id(*)(id, SEL))objc_msgSend)(value, SEL_copy); // copy object
    }
    return value;
}

/**
 * 释放关联对象的值
 */
static void releaseValue(id value, uintptr_t policy) {
    if (policy & OBJC_ASSOCIATION_SETTER_RETAIN) { // 由此可见, 只有强引用retain才会被release操作
        return objc_release(value);
    }
}

struct ReleaseValue {
    void operator() (ObjcAssociation &association) {
        releaseValue(association.value(), association.policy());
    }
};

/**
 * 关联引用对象
 ** Objective-C: objc_setAssociatedObject 底层调用的是 objc_setAssociatedObject_non_gc
 ** 底层: objc_setAssociatedObject_non_gc调用了_object_set_associative_reference
 * object : 被关联对象
 * key    : 可以认为是一个属性名
 * value  : 值
 * policy : 关联策略
 */
void _object_set_associative_reference(id object, void *key, id value, uintptr_t policy) {
    // retain the new value (if any) outside the lock.
    ObjcAssociation old_association(0, nil); // 创建一个关联
    id new_value = value ? acquireValue(value, policy) : nil; // acquireValue判断关联策略类型
    {
        AssociationsManager manager; // 用 mutex_t(互斥锁)维护的AssociationsHashMap哈希表映射; 哈希表可以认为就是个dictionary
        AssociationsHashMap &associations(manager.associations()); // 获取到所有的关联对象
        disguised_ptr_t disguised_object = DISGUISE(object); // 把object对象包装成disguised_ptr_t类型
        if (new_value) {
            // break any existing association.
            // 遍历所有的被关联对象查找 object 对象对应的被关联对象
            AssociationsHashMap::iterator i = associations.find(disguised_object);
            /// end()返回指向map末尾的迭代器, 并非最优一个元素. 如果想获取最后一个元素需要last=end()之后last--,last就是最后一个元素
            if (i != associations.end()) { // i != (末尾迭代器) 代表object之前有过关联
                // secondary table exists
                ObjectAssociationMap *refs = i->second; // 获取键值对i对应的value值, ObjectAssociationMap哈希表映射
                ObjectAssociationMap::iterator j = refs->find(key); // 遍历所有的关联策略查找 key 对应的关联策略
                if (j != refs->end()) { // 存在
                    old_association = j->second; // 缓存之前的值, 在下面会release这个值
                    j->second = ObjcAssociation(policy, new_value); // 把{(}最新值&关联策略}更新
                } else { // 不存在
                    (*refs)[key] = ObjcAssociation(policy, new_value); // 不存在直接根据key赋值{值&关联策略}
                }
            } else { // 不存在, 代表当前对象没有关联过对象, 所以直接创建ObjectAssociationMap储存{值&关联策略}
                // create the new association (first time).
                ObjectAssociationMap *refs = new ObjectAssociationMap; // 创建ObjectAssociationMap
                associations[disguised_object] = refs; // 储存 ObjectAssociationMap
                (*refs)[key] = ObjcAssociation(policy, new_value); // 创建关联策略
                // 储存关联策略
                object->setHasAssociatedObjects();  // data()->flags & RW_INSTANCES_HAVE_ASSOCIATED_OBJECTS;
            }
        } else {
            // setting the association to nil breaks the association.
            // 代表赋值的为nil
            AssociationsHashMap::iterator i = associations.find(disguised_object);
            if (i != associations.end()) { // 存在, 代表之前关联过
                ObjectAssociationMap *refs = i->second; // 找到 对象对应的ObjectAssociationMap
                ObjectAssociationMap::iterator j = refs->find(key); // 遍历查找是否有过赋值
                if (j != refs->end()) { // 如果有需要释放之前的对象
                    old_association = j->second; // 缓存之前的value对象, 后期释放
                    refs->erase(j); // 移除key对应的元素
                }
            }
        }
    }
    // release the old value (outside of the lock).
    if (old_association.hasValue()) ReleaseValue()(old_association); // release之前的关联对象对应的value
}

/**
 * 移除关联对象
 ** Objective-C: objc_removeAssociatedObjects 底层调用的是 _object_remove_assocations
 ** 底层: _object_remove_assocations
 * object : 被关联对象
 */
void _object_remove_assocations(id object) {
    // 全部的关联策略
    vector< ObjcAssociation,ObjcAllocator<ObjcAssociation> > elements;
    {
        AssociationsManager manager;
        AssociationsHashMap &associations(manager.associations());
        if (associations.size() == 0) return; // map中元素的个数为0直接return
        disguised_ptr_t disguised_object = DISGUISE(object);
        AssociationsHashMap::iterator i = associations.find(disguised_object);
        if (i != associations.end()) {
            // copy all of the associations that need to be removed.
            ObjectAssociationMap *refs = i->second;
            for (ObjectAssociationMap::iterator j = refs->begin(), end = refs->end(); j != end; ++j) {
                elements.push_back(j->second);
            }
            // remove the secondary table.
            delete refs; // 释放refs内存
            associations.erase(i); // 从associations 移除object
        }
    }
    // the calls to releaseValue() happen outside of the lock.
    // 遍历移除被关联对象中所有的 AssociationsHashMap 对象,并且对全部对象release
    for_each(elements.begin(), elements.end(), ReleaseValue());
}
